package com.zjsru.oneDay;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 1298. 你能从盒子里获得的最大糖果数
 *
 * @Author: cookLee
 * @Date: 2025-06-03
 */
public class MaxCandies {

    /**
     * 主
     * \
     * 输入：status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]
     * 输出：16
     * 解释：
     * 一开始你有盒子 0 。你将获得它里面的 7 个糖果和盒子 1 和 2。
     * 盒子 1 目前状态是关闭的，而且你还没有对应它的钥匙。所以你将会打开盒子 2 ，并得到里面的 4 个糖果和盒子 1 的钥匙。
     * 在盒子 1 中，你会获得 5 个糖果和盒子 3 ，但是你没法获得盒子 3 的钥匙所以盒子 3 会保持关闭状态。
     * 你总共可以获得的糖果数目 = 7 + 4 + 5 = 16 个。
     * \
     * 输入：status = [1,0,0,0,0,0], candies = [1,1,1,1,1,1], keys = [[1,2,3,4,5],[],[],[],[],[]], containedBoxes = [[1,2,3,4,5],[],[],[],[],[]], initialBoxes = [0]
     * 输出：6
     * 解释：
     * 你一开始拥有盒子 0 。打开它你可以找到盒子 1,2,3,4,5 和它们对应的钥匙。
     * 打开这些盒子，你将获得所有盒子的糖果，所以总糖果数为 6 个。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        MaxCandies maxCandies = new MaxCandies();
        int[] status = new int[]{1, 0, 1, 0};
        int[] candies = new int[]{7, 5, 4, 100};
        int[][] keys = new int[][]{{1, 2}, {3}, {0}};
        int[][] containedBoxes = new int[][]{{1, 2, 3}, {}, {}, {}};
        int[] initialBoxes = new int[]{0};
        System.out.println(maxCandies.maxCandies(status, candies, keys, containedBoxes, initialBoxes));
    }


    public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
        int len = status.length;
        //记录每个盒子是否可打开
        boolean[] canOpen = new boolean[len];
        //表示当前拥有的盒子
        boolean[] hasBox = new boolean[len];
        //防止重复处理同一个盒子
        boolean[] used = new boolean[len];

        //如果 box[i] 是开的，那么是 1 ，否则是 0 。
        for (int i = 0; i < len; i++) {
            canOpen[i] = status[i] == 1;
        }
        Queue<Integer> queue = new LinkedList<>();
        int ans = 0;
        for (int i = 0; i < initialBoxes.length; i++) {
            hasBox[initialBoxes[i]] = true;
            if (canOpen[initialBoxes[i]]) {
                queue.offer(initialBoxes[i]);
                used[initialBoxes[i]] = true;
                ans += candies[initialBoxes[i]];
            }
        }
        //打开盒子后获取其内部的钥匙和子盒子
        while (!queue.isEmpty()) {
            Integer poll = queue.poll();
            if (poll >= keys.length || poll < 0) {
                continue;
            }
            for (int key : keys[poll]) {
                canOpen[key] = true;
                if (!used[key] && hasBox[key]) {
                    queue.offer(key);
                    used[key] = true;
                    ans += candies[key];
                }
            }
            for (int box : containedBoxes[poll]) {
                hasBox[box] = true;
                if (canOpen[box] && !used[box]) {
                    queue.offer(box);
                    used[box] = true;
                    ans += candies[box];
                }
            }
        }
        return ans;
    }

}
